"""
Exercise 2.
An ant is trying to get from point A to point B in a grid; see Figure 2. The coordinates of point A is (1,1) (this is top left corner), and the coordinates of point B is (n,n) (this is bottom right corner, n is the size of the grid).
Once the ant starts moving, there are four options, it can go left, right, up or down (no diagonal movement allowed). If any of these four options satisfy the following:
(a) The new point should still be within the boundaries of the n×n grid
(b) Only the center point (4, 4) is allowed to be visited zero, one or two times, while the remainder points should not be visited previously (are allowed to be visited zero or one time).
If P is the probability of the ant reaching point B for a 7×7 grid, use Monte Carlo simulation to compute P. Pick the answer closest to P in value (assume 20,000 simulations are sufficient enough to compute P).

Author: Zhang Jinwei
"""
import random as rd
import numpy as np
import copy

the_map = np.array([[0, 1, 1, 1, 1, 1, 1]
                    , [1, 1, 1, 1, 1, 1, 1]
                    , [1, 1, 1, 1, 1, 1, 1]
                    , [1, 1, 1, 2, 1, 1, 1]
                    , [1, 1, 1, 1, 1, 1, 1]
                    , [1, 1, 1, 1, 1, 1, 1]
                    , [1, 1, 1, 1, 1, 1, 9]])

route_map = np.array([[0, '*', '*', '*', '*', '*', '*']
                    , ['*', '*', '*', '*', '*', '*', '*']
                    , ['*', '*', '*', '*', '*', '*', '*']
                    , ['*', '*', '*', '*', '*', '*', '*']
                    , ['*', '*', '*', '*', '*', '*', '*']
                    , ['*', '*', '*', '*', '*', '*', '*']
                    , ['*', '*', '*', '*', '*', '*', '*']])


def loc_check(pos):
    for i in pos:
        if i < 0 or i > 6:
            return False
    return True

class Ant:
    def __init__(self,  a_map, route):
        self.pos = [0, 0]
        self.a_map = copy.deepcopy(a_map)
        self.route = copy.deepcopy(route)
        self.curr_choice = [[0, 0]]
        self.move_cnt = 0

    def avaliable_direction(self):
        turn_choice0 = [np.array([-1, 0]), np.array([1, 0]), np.array([0, -1]), np.array([0, 1])]

        pos_up, pos_down, pos_left, pos_right = \
            np.array(self.pos) +np.array([-1, 0]), np.array(self.pos) +np.array([1, 0]),np.array(self.pos) +np.array([0, -1]),np.array(self.pos) +np.array([0, 1])
        turn_choice1 = [pos_up, pos_down, pos_left, pos_right]
        turn_choice3 = []

        for i in range(len(turn_choice1)):
            if loc_check(turn_choice1[i]):  # 返回不撞墙的可能选择
                val = self.a_map[turn_choice1[i][0]][turn_choice1[i][1]]
                if val > 0:  # 不走回头路的选择
                    # print(turn_choice1)
                    turn_choice3.append(turn_choice0[i])
        if not turn_choice3:
            return False  # Failed 周围的路都走过了
        # print(3, turn_choice3)
        return turn_choice3  # 返回当前可选方向

    def walk(self):
        avaliable_direction = self.avaliable_direction()
        # print(self.move_cnt, avaliable_direction)
        if avaliable_direction:
            move = np.array(rd.choice(avaliable_direction))
        else:
            # print(self.a_map)
            return False  # 失败，终止
        # print(100, move)
        self.pos = np.array(self.pos) + move
        self.a_map[self.pos[0]][self.pos[1]] -= 1
        self.move_cnt += 1
        self.route[self.pos[0]][self.pos[1]] = self.move_cnt
        if self.pos[0] == 6 and self.pos[1] == 6:

            return False  # 成功，终止
        return True


def simulation(ant_x, show_route=True):
    """
    :param ant_x: 实例化的Ant
    :param show_route: 选择是否打印路线图
    :return: 走通1，失败0
    """
    while True:
        status = ant_x.walk()
        if not status:
            break
    val = ant_x.a_map[6][6]
    if val == 8:
        if show_route:
            print('Succeed' + '\n', ant_x.route)
        return 1
    else:
        if show_route:
            print('Failed' + '\n', ant_x.route)
        return 0


if __name__ == '__main__':
    for i in range(10):
        trail = 20000
        success_cnt = 0
        for i in range(trail):
            ant_x = Ant(the_map, route_map)
            result = simulation(ant_x, show_route=False)
            success_cnt += result
        print('Took %d Trail, success %d times, success rate = %0.06f' % (trail, success_cnt, success_cnt/trail) )



